number_list = [0, 1, 2, 3, 4, 5, 6, 7]


def linear_search_v1(value, iterable):
    for index, val in enumerate(iterable):  # 返回index位置和value值
        if val == value:
            return index
    return -1


def linear_search_v2(f, iterable):
    for index, val in enumerate(iterable):
        if f(val):
            return index
    return -1


def binary_search(sorted_array, val):
    if not sorted_array or len(sorted_array) == 0:
        return -1
    begin = 0
    end = len(sorted_array) - 1
    while begin <= end:
        mid = int((begin + end) / 2)  # mid取值会向下取1.5取值只有1
        if sorted_array[mid] == val:
            return mid
        elif sorted_array[mid] < val:  # 必须要 + - 1不然在[1,2]会进入死循环
            begin = mid + 1
        elif sorted_array[mid] > val:
            end = mid - 1
    return -1


def binary_search_v2(sorted_array, begin, end, val):

    mid = int((begin + end) / 2)
    if sorted_array[mid] == val:
        return mid
    elif sorted_array[mid] < val:
        return binary_search_v2(sorted_array, mid + 1, end, val)
    elif sorted_array[mid] > val:
        return binary_search_v2(sorted_array, begin, mid - 1, val)


def test_liner_search():
    assert linear_search_v1(5, number_list) == 5
    assert linear_search_v2(lambda x: x == 6, number_list) == 6
    assert binary_search([2, 3, 5, 7], 5) == 2
    assert binary_search([2, 3, 5, 7], 2) == 0
    assert binary_search([2, 3, 5, 7], 8) == -1
    assert binary_search([2, 3, 7], 3) == 1
    assert binary_search([], 8) == -1
    assert binary_search(None, 8) == -1

    a = list(range(10))
    for i in a:
        assert binary_search_v2(a, 0, 9, i) == i

